package chapter02_linkedList;

import com.sun.istack.internal.localization.NullLocalizable;

import java.util.Currency;
import java.util.Stack;

/**
 * 描述：
 *      加两个链表组成的数相加，返回结果的链表，链表的每个结点的取值范围在0~9
 * @author hl
 * @date 2021/1/29 10:47
 */
public class AddList {
    /**
     * 利用栈求解
     * @param node1
     * @param node2
     * @return
     */
    public Node addLists1(Node node1, Node node2){
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        while(node1 != null){
            stack1.push(node1.val);
            node1 = node1.next;
        }
        while(node2 != null){
            stack2.push(node2.val);
            node2 = node2.next;
        }
        int cn = 0;
        int n1 = 0;
        int n2 = 0;
        int n = 0;
        Node pre = null;
        Node node = null;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            n1 = stack1.isEmpty() ? 0 : stack1.pop();
            n2 = stack2.isEmpty() ? 0 : stack2.pop();
            n = n1 + n2 + cn;
            pre = node;
            node = new Node(n % 10);
            node.next = pre;
            cn = n / 10;
        }
        if (cn != 0) {
            pre = node;
            node = new Node(cn);
            node.next = pre;
        }
        return node;
    }

    /**
     * 逆序链表求和
     * 空间复杂度O(1)
     * @param head1
     * @param head2
     * @return
     */
    public Node addLists2(Node head1, Node head2){
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        Node pre = null;
        int n1 = 0;
        int n2 = 0;
        int n = 0;
        int cn = 0;
        Node node = null;
        while(head1 != null || head2 != null){
            n1 = head1 == null ? 0 : head1.val;
            n2 = head2 == null ? 0 : head2.val;
            n = (n1 + n2 + cn);
            pre = node;
            node = new Node(n % 10);
            node.next = pre;
            cn = n / 10;
            if (head1 != null) {
                head1 = head1.next;
            }
            if (head2 != null) {
                head2 = head2.next;
            }
        }
        if (cn != 0) {
            pre = node;
            node = new Node(cn);
            node.next = pre;
        }
        return node;
    }

    private Node reverseList(Node node1) {
        Node pre = null;
        Node next = null;
        while(node1 != null){
            next = node1.next;
            node1.next = pre;
            pre = node1;
            node1 = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        Node node1 = new Node(4);
        node1.next = new Node(6);
        node1.next.next = new Node(8);

        Node node2 = new Node(7);
        node2.next = new Node(4);
        node2.next.next = new Node(4);
        new AddList().addLists2(node1, node2);
    }

}
